package com.javaDemo.ti;

/**
 * 字符串反转器
 * 
 * @author csy
 * @description 实现字符串中单词的反转，同时处理多余的空格
 * 
 *              解题思路：
 *              1. 去除字符串首尾以及中间多余的空格
 *              2. 反转整个字符串
 *              3. 再反转每个单词
 * 
 *              实现细节：
 *              1. 使用StringBuilder进行字符串操作，提高效率
 *              2. 使用双指针法进行字符串反转
 *              3. 不使用Java内置的split等方法，实现更高的性能
 * 
 *              时间复杂度：O(n)，其中n是字符串长度
 *              空间复杂度：O(n)，需要StringBuilder存储处理后的字符串
 * 
 *              示例：
 *              输入：" the sky is blue "
 *              输出："blue is sky the"
 * 
 *              参考：https://programmercarl.com/0151.翻转字符串里的单词.html
 */
public class StringReverser {

    /**
     * 反转字符串中的单词
     *
     * @param input 输入的字符串
     * @return 反转单词后的字符串
     */
    public static String reverseWords(String input) {
        // 1. 去除多余空格
        StringBuilder cleanStr = removeExtraSpaces(input);
        // 2. 反转整个字符串
        reverseString(cleanStr, 0, cleanStr.length() - 1);
        // 3. 反转每个单词
        reverseEachWord(cleanStr);

        return cleanStr.toString();
    }

    /**
     * 去除字符串中多余的空格
     * 1. 去除开头和结尾的空格
     * 2. 单词间只保留一个空格
     *
     * @param input 原始字符串
     * @return 处理后的StringBuilder
     */
    private static StringBuilder removeExtraSpaces(String input) {
        StringBuilder result = new StringBuilder();
        int start = 0;
        int end = input.length() - 1;

        // 找到第一个非空格字符
        while (start <= end && input.charAt(start) == ' ') {
            start++;
        }

        // 找到最后一个非空格字符
        while (end >= start && input.charAt(end) == ' ') {
            end--;
        }

        // 处理中间的空格
        while (start <= end) {
            char currentChar = input.charAt(start);

            // 当前字符不是空格，或者结果串最后一个字符不是空格时，添加字符
            if (currentChar != ' ' ||
                    (result.length() > 0 && result.charAt(result.length() - 1) != ' ')) {
                result.append(currentChar);
            }

            start++;
        }

        return result;
    }

    /**
     * 反转每个单词
     * 通过空格确定单词的边界，然后反转每个单词
     *
     * @param str 待处理的字符串
     */
    private static void reverseEachWord(StringBuilder str) {
        int start = 0;
        int end = 1;
        int length = str.length();

        while (start < length) {
            // 找到单词的结束位置
            while (end < length && str.charAt(end) != ' ') {
                end++;
            }

            // 反转当前单词
            reverseString(str, start, end - 1);

            // 移动到下一个单词
            start = end + 1;
            end = start + 1;
        }
    }

    /**
     * 反转字符串指定区间的字符
     *
     * @param str   待反转的字符串
     * @param start 起始位置（包含）
     * @param end   结束位置（包含）
     */
    private static void reverseString(StringBuilder str, int start, int end) {
        while (start < end) {
            // 交换字符
            char temp = str.charAt(start);
            str.setCharAt(start, str.charAt(end));
            str.setCharAt(end, temp);

            // 移动指针
            start++;
            end--;
        }
    }

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试用例
        String[] testCases = {
                "the sky is blue",
                "  hello world  ",
                "a good   example",
                "  Bob    Loves  Alice   "
        };

        // 执行测试
        for (String test : testCases) {
            String result = reverseWords(test);
            System.out.printf("输入：\"%s\"%n输出：\"%s\"%n%n",
                    test, result);
        }
    }
}